package fun.ticsmyc.question;

/**
 * leetcode 4. 寻找两个正序数组的中位数
 * @author Ticsmyc
 * @package fun.ticsmyc.question
 * @date 2021-02-04 15:52
 */
public class 两个有序数组的中位数 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length = nums1.length+nums2.length;
        if(length %2 ==1){
            //奇数
            return findKth(nums1,nums2,length/2+1);
        }else {
            //偶数
            return ((double)findKth(nums1,nums2,length/2)+findKth(nums1,nums2,length/2+1))/2;
        }
    }

    public int findKth(int[] nums1,int[] nums2,int k ) {
        int i1 = 0;
        int i2 = 0;

        while (true) {
            if (i1 == nums1.length) {
                return nums2[i2 + k - 1];
            }
            if (i2 == nums2.length) {
                return nums1[i1 + k - 1];
            }
            if (k == 1) {
                //删掉k-1个数后，第k个即为所求
                return nums1[i1] < nums2[i2] ? nums1[i1] : nums2[i2];
            }

            //本次可以删除的长度
            int deleteLen = k / 2;
            //删除后，两个数组新的下标
            int di1 = Math.min(i1 + deleteLen, nums1.length) - 1;
            int di2 = Math.min(i2 + deleteLen, nums2.length) - 1;

            //删除较小的那个数组
            if (nums1[di1] < nums2[di2]) {
                k -= di1 - i1 + 1;
                i1 = di1 + 1;
            } else {
                k -= di2 - i2 + 1;
                i2 = di2 + 1;
            }
        }
    }
}
